A finite state transducer (FST) which is a kind of finite state automation (FSA) is used in various fields, such as natural language processing or speech recognition. Formally, the FST is expressed by a six-tuple (Q, Σ, Δ, E, I, F). Q denotes a set of states, Σ denotes a set of input symbols, E denotes a set of transitions, I denotes a set of initial states, F denotes a set of final states, and Δ denotes a set of output symbols. In the FST, the transition E is EQ×Σ×Δ*×Q. Δ* is the Kleene closure of Δ, and refers to a set of all symbol sequences which can be created by combinations of null symbol sequences ε and Δ. If the output symbols are excluded from the FST, the FSA is implemented. The FST is also called a generalized sequential machine.
When the FST is nondeterministic, this means that the same input symbol sequence is assigned to a plurality of paths. Formally, this means that, when the size of a set X (the number of components) is expressed by |X|, and a set of paths which can be transited from a state qεQ by an input symbol sequence wεΣ* is Π(q,w)E*, there is q such that the condition |Π(q,w)|>1 is satisfied. This FST is referred to as a nondeterministic finite state transducer (NFST). Meanwhile, when the FST is deterministic, this means that there is only one path to the maximum when a certain input symbol sequence is applied. Formally, this means that the condition |Π(q,w)|≦1 is satisfied for all of qεQ and wεΣ*. This FST is referred to as a deterministic finite state transducer (DFST). Conversion of NFST to DFST is referred to as determinizing. The determinizing is carried out, for example, by a method described in U.S. Pat. No. 6,456,971 or M. Mohri, “On Some Applications of Finite-State Automata Theory to Natural Language Processing,” Natural Language Engineering, 1996, vol. 2, issue 1, Pages 61-80.
However, in determinizing a non-single-valued NFST by the method of the related art, it is necessary to perform preprocessing, which includes a step of finding a portion responsible for a non-single value and a step of converting the found portion to a single value to form a single-valued NFST (“single value” will be described below).